home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CUJ9102.ARJ / 9N02058A < prev    next >
Text File  |  1992-07-06  |  25KB  |  595 lines
  1.  
  2. /***********************************************************
  3.  *  Node-Positioning for General Trees, by John Q. Walker II
  4.  *
  5.  *  Initiated by calling procedure TreePosition().
  6.  **********************************************************/
  7.  
  8. #include <stdlib.h>
  9.  
  10. /*----------------------------------------------------------
  11.  * Implementation dependent: Set the values for each of
  12.  * these variables.
  13.  *--------------------------------------------------------*/
  14. #define NODE_WIDTH          20  /* Width of a node?       */
  15. #define NODE_HEIGHT         10  /* Height of a node?      */
  16. #define FRAME_THICKNESS     1   /* Fixed-sized node frame?*/
  17. #define SUBTREE_SEPARATION  5   /* Gap between subtrees?  */
  18. #define SIBLING_SEPARATION  4   /* Gap between siblings?  */
  19. #define LEVEL_SEPARATION    5   /* Gap between levels?    */
  20. #define MAXIMUM_DEPTH       10  /* Biggest tree?          */
  21.  
  22. /*----------------------------------------------------------
  23.  * Implementation dependent: The structure for one node
  24.  * - The first 4 pointers must be set for each node before
  25.  *   this algorithm is called.
  26.  * - The X and Y coordinates must be set for only the apex
  27.  *   of the tree upon entry; they will be set by this
  28.  *   algorithm for all the other nodes.
  29.  * - The next three elements are used only for the duration
  30.  *   of the algorithm.
  31.  * - Actual contents of the node depend on your application.
  32.  *--------------------------------------------------------*/
  33. typedef int COORD;              /* X,Y coordinate type    */
  34.  
  35. typedef struct node {
  36.     struct node *parent;        /* ptr: node's parent     */
  37.     struct node *offspring;     /* ptr: leftmost child    */
  38.     struct node *leftsibling;   /* ptr: sibling on left   */
  39.     struct node *rightsibling;  /* ptr: sibling on right  */
  40.     COORD  xCoordinate;         /* node's current x coord */
  41.     COORD  yCoordinate;         /* node's current y coord */
  42.  
  43.     struct node *prev;          /* ptr: lefthand neighbor */
  44.     float  flPrelim;            /* preliminary x coord    */
  45.     float  flModifier;          /* temporary modifier     */
  46.  
  47.     char   info[80];            /* pick your contents!    */
  48. } *PNODE;                       /* ptr: a node structure  */
  49.  
  50. /*----------------------------------------------------------
  51.  * Global variables used by the algorithm
  52.  *--------------------------------------------------------*/
  53. typedef enum { FALSE, TRUE } BOOL;
  54. typedef enum { FRAME, NO_FRAME } FRAME_TYPE;
  55. typedef enum { NORTH, SOUTH, EAST, WEST } ROOT_ORIENTATION;
  56.  
  57. typedef struct prev_node {      /* one list element       */
  58.     PNODE pPreviousNode;        /* ptr: previous at level */
  59.     struct prev_node *pNextLevel;   /* ptr: next element  */
  60. } *PPREVIOUS_NODE;
  61.  
  62. static FRAME_TYPE FrameType = FRAME;    /* Show a frame   */
  63. static ROOT_ORIENTATION RootOrientation = NORTH; /* At top*/
  64. static PPREVIOUS_NODE pLevelZero = (PPREVIOUS_NODE)0;
  65.  
  66. static COORD xTopAdjustment;    /* How to adjust the apex */
  67. static COORD yTopAdjustment;    /* How to adjust the apex */
  68. static float flMeanWidth;       /* Ave. width of 2 nodes  */
  69.  
  70. #define FIRST_TIME  (0)         /* recursive proc flag    */
  71.  
  72. /*----------------------------------------------------------
  73.  * Implemented as macros, but could be implemented as
  74.  * procedures depending on your particular node structures
  75.  *--------------------------------------------------------*/
  76. #define FirstChild(node)     ((PNODE)((node)->offspring))
  77. #define LeftSibling(node)    ((PNODE)((node)->leftsibling))
  78. #define RightSibling(node)   ((PNODE)((node)->rightsibling))
  79. #define Parent(node)         ((PNODE)((node)->parent))
  80. #define LeftNeighbor(node)   ((PNODE)((node)->prev))
  81. #define IsLeaf(node)          \
  82.                (((node)&&(!((node)->offspring)))?TRUE:FALSE)
  83. #define HasChild(node)        \
  84.                   (((node)&&((node)->offspring))?TRUE:FALSE)
  85. #define HasLeftSibling(node)  \
  86.                 (((node)&&((node)->leftsibling))?TRUE:FALSE)
  87. #define HasRightSibling(node) \
  88.                (((node)&&((node)->rightsibling))?TRUE:FALSE)
  89.  
  90.  
  91. static PNODE GetPrevNodeAtLevel (unsigned nLevelNbr)
  92. {
  93.     /*------------------------------------------------------
  94.      * List Manipulation: Return pointer to previous node at
  95.      * this level
  96.      *----------------------------------------------------*/
  97.     PPREVIOUS_NODE pTempNode;   /* used in the for-loop   */
  98.     unsigned  i = 0;            /* level counter          */
  99.  
  100.     for (pTempNode = pLevelZero; (pTempNode);
  101.          pTempNode = pTempNode->pNextLevel) {
  102.         if (i++ == nLevelNbr)
  103.             /* Reached desired level.  Return its pointer */
  104.             return (pTempNode->pPreviousNode);
  105.     }
  106.     return ((PNODE)0);  /* No pointer yet for this level. */
  107. }
  108.  
  109. static BOOL SetPrevNodeAtLevel (unsigned nLevelNbr,
  110.                                 PNODE pThisNode)
  111. {
  112.     /*------------------------------------------------------
  113.      * List Manipulation: Set the list element to the
  114.      * previous node at this level
  115.      *----------------------------------------------------*/
  116.  
  117.     PPREVIOUS_NODE pTempNode;   /* used in the for-loop   */
  118.     PPREVIOUS_NODE pNewNode;    /* newly-allocated memory */
  119.     unsigned  i = 0;            /* level counter          */
  120.  
  121.     for (pTempNode = pLevelZero; (pTempNode);
  122.          pTempNode = pTempNode->pNextLevel) {
  123.         if (i++ == nLevelNbr) {
  124.             /* Reached desired level.  Return its pointer */
  125.             pTempNode->pPreviousNode = pThisNode;
  126.             return (TRUE);
  127.         }
  128.         else if (pTempNode->pNextLevel==(PPREVIOUS_NODE)0) {
  129.             /* Looks like we need a new level: add it.    */
  130.             /* We need to keep going--should be the next. */
  131.             pNewNode = (PPREVIOUS_NODE)
  132.                        malloc(sizeof(struct prev_node));
  133.             if (pNewNode) {
  134.                 pNewNode->pPreviousNode = (PNODE)0;
  135.                 pNewNode->pNextLevel = (PPREVIOUS_NODE)0;
  136.                 pTempNode->pNextLevel = pNewNode;
  137.             }
  138.             else return (FALSE);    /* The malloc failed. */
  139.         }
  140.     }
  141.  
  142.     /* Should only get here if pLevelZero is 0.           */
  143.     pLevelZero = (PPREVIOUS_NODE)
  144.                  malloc(sizeof(struct prev_node));
  145.     if (pLevelZero) {
  146.         pLevelZero->pPreviousNode = pThisNode;
  147.         pLevelZero->pNextLevel = (PPREVIOUS_NODE)0;
  148.         return (TRUE);
  149.     }
  150.     else return (FALSE);        /* The malloc() failed.   */
  151. }
  152.  
  153. static void InitPrevNodeAtLevel (void)
  154. {
  155.     /*------------------------------------------------------
  156.      * List Manipulation: Initialize the list of the
  157.      * previous node at each level to all zeros.
  158.      *----------------------------------------------------*/
  159.  
  160.     PPREVIOUS_NODE pTempNode = pLevelZero;  /* the start  */
  161.  
  162.     for ( ; (pTempNode); pTempNode = pTempNode->pNextLevel)
  163.         pTempNode->pPreviousNode = (PNODE)0;
  164. }
  165.  
  166. static BOOL CheckExtentsRange(long lxTemp, long lyTemp)
  167. {
  168.     /*------------------------------------------------------
  169.      * Insert your own code here, to check when the
  170.      * tree drawing is going to be too big.  My region is no
  171.      * more that 64000 units square.
  172.      *----------------------------------------------------*/
  173.  
  174.     if ((labs(lxTemp) > 32000) || (labs(lyTemp) > 32000))
  175.         return (FALSE);
  176.     else
  177.         return (TRUE);
  178. }
  179.  
  180. static void TreeMeanNodeSize (PNODE pLeftNode,
  181.                               PNODE pRightNode)
  182. {
  183.     /*------------------------------------------------------
  184.      * Write your own code for this procedure if your
  185.      * rendered nodes will have variable sizes.
  186.      *------------------------------------------------------
  187.      * Here I add the width of the contents of the
  188.      * right half of the pLeftNode to the left half of the
  189.      * right node.  Since the size of the contents for all
  190.      * nodes is currently the same, this module computes the
  191.      * following trivial computation.
  192.      *----------------------------------------------------*/
  193.  
  194.     flMeanWidth = (float)0.0;   /* Initialize this global */
  195.  
  196.     switch (RootOrientation) {
  197.         case NORTH:
  198.         case SOUTH:
  199.             if (pLeftNode) {
  200.                 flMeanWidth = flMeanWidth +
  201.                               (float)(NODE_WIDTH/2);
  202.                 if (FrameType != NO_FRAME)
  203.                     flMeanWidth = flMeanWidth +
  204.                                   (float)FRAME_THICKNESS;
  205.             }
  206.             if (pRightNode) {
  207.                 flMeanWidth = flMeanWidth +
  208.                               (float)(NODE_WIDTH/2);
  209.                 if (FrameType != NO_FRAME)
  210.                     flMeanWidth = flMeanWidth +
  211.                                   (float)FRAME_THICKNESS;
  212.             }
  213.             break;
  214.         case EAST :
  215.         case WEST :
  216.             if (pLeftNode) {
  217.                 flMeanWidth = flMeanWidth +
  218.                               (float)(NODE_HEIGHT/2);
  219.                 if (FrameType != NO_FRAME)
  220.                     flMeanWidth = flMeanWidth +
  221.                                   (float)FRAME_THICKNESS;
  222.             }
  223.             if (pRightNode) {
  224.                 flMeanWidth = flMeanWidth +
  225.                               (float)(NODE_HEIGHT/2);
  226.                 if (FrameType != NO_FRAME)
  227.                     flMeanWidth = flMeanWidth +
  228.                                   (float)FRAME_THICKNESS;
  229.             }
  230.             break;
  231.     }
  232. }
  233.  
  234. static PNODE TreeGetLeftmost(PNODE pThisNode,
  235.                              unsigned nCurrentLevel,
  236.                              unsigned nSearchDepth)
  237. {
  238.     /*------------------------------------------------------
  239.      * Determine the leftmost descendant of a node at a
  240.      * given depth.  This is implemented using a post-order
  241.      * walk of the subtree under pThisNode, down to the
  242.      * level of nSearchDepth.  If we've searched to the
  243.      * proper distance, return the currently leftmost node.
  244.      * Otherwise, recursively look at the progressively
  245.      * lower levels.
  246.      *----------------------------------------------------*/
  247.  
  248.     PNODE pLeftmost;    /* leftmost descendant at level   */
  249.     PNODE pRightmost;   /* rightmost offspring in search  */
  250.  
  251.     if (nCurrentLevel == nSearchDepth)
  252.         pLeftmost = pThisNode;  /* searched far enough.   */
  253.     else if (IsLeaf(pThisNode))
  254.         pLeftmost = 0;  /* This node has no descendants   */
  255.     else {  /* Do a post-order walk of the subtree.       */
  256.         for (pLeftmost = TreeGetLeftmost(pRightmost =
  257.                                 FirstChild(pThisNode),
  258.                                 nCurrentLevel + 1,
  259.                                 nSearchDepth)
  260.             ;
  261.             (pLeftmost==0) && (HasRightSibling(pRightmost))
  262.             ;
  263.             pLeftmost = TreeGetLeftmost(pRightmost =
  264.                                 RightSibling(pRightmost),
  265.                                 nCurrentLevel + 1,
  266.                                 nSearchDepth)
  267.            ) { /* Nothing inside this for-loop. */ }
  268.     }
  269.     return (pLeftmost);
  270. }
  271.  
  272. static void TreeApportion (PNODE pThisNode,
  273.                            unsigned nCurrentLevel)
  274. {
  275.     /*------------------------------------------------------
  276.      * Clean up the positioning of small sibling subtrees.
  277.      * Subtrees of a node are formed independently and
  278.      * placed as close together as possible.  By requiring
  279.      * that the subtrees be rigid at the time they are put
  280.      * together, we avoid the undesirable effects that can
  281.      * accrue from positioning nodes rather than subtrees.
  282.      *----------------------------------------------------*/
  283.  
  284.     PNODE pLeftmost;            /* leftmost at given level*/
  285.     PNODE pNeighbor;            /* node left of pLeftmost */
  286.     PNODE pAncestorLeftmost;    /* ancestor of pLeftmost  */
  287.     PNODE pAncestorNeighbor;    /* ancestor of pNeighbor  */
  288.     PNODE pTempPtr;             /* loop control pointer   */
  289.     unsigned i;                 /* loop control           */
  290.     unsigned nCompareDepth;     /* depth of comparison    */
  291.                                 /* within this proc       */
  292.     unsigned nDepthToStop;      /* depth to halt          */
  293.     unsigned nLeftSiblings;     /* nbr of siblings to the */
  294.              /* left of pThisNode, including pThisNode,   */
  295.              /* til the ancestor of pNeighbor             */
  296.     float flLeftModsum;         /* sum of ancestral mods  */
  297.     float flRightModsum;        /* sum of ancestral mods  */
  298.     float flDistance;           /* difference between     */
  299.           /* where pNeighbor thinks pLeftmost should be   */
  300.           /* and where pLeftmost actually is              */
  301.     float flPortion;            /* proportion of          */
  302.           /* flDistance to be added to each sibling       */
  303.  
  304.     pLeftmost = FirstChild(pThisNode);
  305.     pNeighbor = LeftNeighbor(pLeftmost);
  306.  
  307.     nCompareDepth = 1;
  308.     nDepthToStop = MAXIMUM_DEPTH - nCurrentLevel;
  309.  
  310.     while ((pLeftmost) && (pNeighbor) &&
  311.            (nCompareDepth <= nDepthToStop)) {
  312.  
  313.         /* Compute the location of pLeftmost and where it */
  314.         /* should be with respect to pNeighbor.           */
  315.         flRightModsum = flLeftModsum = (float)0.0;
  316.         pAncestorLeftmost = pLeftmost;
  317.         pAncestorNeighbor = pNeighbor;
  318.         for (i = 0; (i < nCompareDepth); i++) {
  319.             pAncestorLeftmost = Parent(pAncestorLeftmost);
  320.             pAncestorNeighbor = Parent(pAncestorNeighbor);
  321.             flRightModsum = flRightModsum +
  322.                             pAncestorLeftmost->flModifier;
  323.             flLeftModsum  = flLeftModsum  +
  324.                             pAncestorNeighbor->flModifier;
  325.         }
  326.  
  327.         /* Determine the flDistance to be moved, and apply*/
  328.         /* it to "pThisNode's" subtree.  Apply appropriate*/
  329.         /* portions to smaller interior subtrees          */
  330.  
  331.         /* Set the global mean width of these two nodes   */
  332.         TreeMeanNodeSize(pLeftmost, pNeighbor);
  333.  
  334.         flDistance = (pNeighbor->flPrelim +
  335.                       flLeftModsum +
  336.                       (float)SUBTREE_SEPARATION +
  337.                       (float)flMeanWidth) -
  338.                      (pLeftmost->flPrelim + flRightModsum);
  339.  
  340.         if (flDistance > (float)0.0) {
  341.             /* Count the interior sibling subtrees        */
  342.             nLeftSiblings = 0;
  343.             for (pTempPtr = pThisNode;
  344.                   (pTempPtr) &&
  345.                   (pTempPtr != pAncestorNeighbor);
  346.                  pTempPtr = LeftSibling(pTempPtr)) {
  347.                 nLeftSiblings++;
  348.             }
  349.  
  350.             if (pTempPtr) {
  351.                 /* Apply portions to appropriate          */
  352.                 /* leftsibling subtrees.                  */
  353.                 flPortion = flDistance/(float)nLeftSiblings;
  354.                 for (pTempPtr = pThisNode;
  355.                      (pTempPtr != pAncestorNeighbor);
  356.                      pTempPtr = LeftSibling(pTempPtr)) {
  357.                     pTempPtr->flPrelim =
  358.                          pTempPtr->flPrelim + flDistance;
  359.                     pTempPtr->flModifier =
  360.                          pTempPtr->flModifier + flDistance;
  361.                     flDistance = flDistance - flPortion;
  362.                 }
  363.             }
  364.             else {
  365.                 /* Don't need to move anything--it needs  */
  366.                 /* to be done by an ancestor because      */
  367.                 /* pAncestorNeighbor and                  */
  368.                 /* pAncestorLeftmost are not siblings of  */
  369.                 /* each other.                            */
  370.                 return;
  371.             }
  372.         }   /* end of the while                           */
  373.  
  374.         /* Determine the leftmost descendant of pThisNode */
  375.         /* at the next lower level to compare its         */
  376.         /* positioning against that of its pNeighbor.     */
  377.         nCompareDepth++;
  378.         if (IsLeaf(pLeftmost))
  379.             pLeftmost = TreeGetLeftmost(pThisNode, 0,
  380.                                          nCompareDepth);
  381.         else
  382.             pLeftmost = FirstChild(pLeftmost);
  383.         pNeighbor = LeftNeighbor(pLeftmost);
  384.     }
  385. }
  386.  
  387. static BOOL TreeFirstWalk(PNODE pThisNode,
  388.                           unsigned nCurrentLevel)
  389. {
  390.     /*------------------------------------------------------
  391.      * In a first post-order walk, every node of the tree is
  392.      * assigned a preliminary x-coordinate (held in field
  393.      * node->flPrelim).  In addition, internal nodes are
  394.      * given modifiers, which will be used to move their
  395.      * children to the right (held in field
  396.      * node->flModifier).
  397.      * Returns: TRUE if no errors, otherwise returns FALSE.
  398.      *----------------------------------------------------*/
  399.  
  400.     PNODE pLeftmost;            /* left- & rightmost      */
  401.     PNODE pRightmost;           /* children of a node.    */
  402.     float flMidpoint;           /* midpoint between left- */
  403.                                 /* & rightmost children   */
  404.  
  405.     /* Set up the pointer to previous node at this level  */
  406.     pThisNode->prev = GetPrevNodeAtLevel(nCurrentLevel);
  407.  
  408.     /* Now we're it--the previous node at this level      */
  409.     if (!(SetPrevNodeAtLevel(nCurrentLevel, pThisNode)))
  410.         return (FALSE);        /* Can't allocate element  */
  411.  
  412.     /* Clean up old values in a node's flModifier         */
  413.     pThisNode->flModifier = (float)0.0;
  414.  
  415.     if ((IsLeaf(pThisNode)) ||
  416.         (nCurrentLevel == MAXIMUM_DEPTH)) {
  417.         if (HasLeftSibling(pThisNode)) {
  418.             /*---------------------------------------------
  419.              * Determine the preliminary x-coordinate
  420.              *   based on:
  421.              * - preliminary x-coordinate of left sibling,
  422.              * - the separation between sibling nodes, and
  423.              * - mean width of left sibling & current node.
  424.              *--------------------------------------------*/
  425.             /* Set the mean width of these two nodes      */
  426.             TreeMeanNodeSize(LeftSibling(pThisNode),
  427.                              pThisNode);
  428.  
  429.             pThisNode->flPrelim =
  430.                         (pThisNode->leftsibling->flPrelim) +
  431.                         (float)SIBLING_SEPARATION +
  432.                         flMeanWidth;
  433.         }
  434.         else    /* no sibling on the left to worry about  */
  435.             pThisNode->flPrelim = (float)0.0;
  436.     }
  437.     else {
  438.         /* Position the leftmost of the children          */
  439.         if (TreeFirstWalk(pLeftmost = pRightmost =
  440.                           FirstChild(pThisNode),
  441.                           nCurrentLevel + 1)) {
  442.             /* Position each of its siblings to its right */
  443.             while (HasRightSibling(pRightmost)) {
  444.                 if (TreeFirstWalk(pRightmost =
  445.                                   RightSibling(pRightmost),
  446.                                   nCurrentLevel + 1)) {
  447.                 }
  448.                 else return (FALSE); /* malloc() failed   */
  449.             }
  450.  
  451.             /* Calculate the preliminary value between    */
  452.             /* the children at the far left and right     */
  453.             flMidpoint = (pLeftmost->flPrelim +
  454.                           pRightmost->flPrelim)/(2.0);
  455.  
  456.             /* Set global mean width of these two nodes   */
  457.             TreeMeanNodeSize(LeftSibling(pThisNode),
  458.                              pThisNode);
  459.  
  460.             if (HasLeftSibling(pThisNode)) {
  461.                 pThisNode->flPrelim =
  462.                        (pThisNode->leftsibling->flPrelim) +
  463.                                  (float)SIBLING_SEPARATION +
  464.                                  flMeanWidth;
  465.  
  466.                 pThisNode->flModifier =
  467.                      pThisNode->flPrelim - flMidpoint;
  468.                 TreeApportion(pThisNode, nCurrentLevel);
  469.             }
  470.             else pThisNode->flPrelim = flMidpoint;
  471.         }
  472.         else return (FALSE); /* Couldn't get an element   */
  473.     }
  474.     return (TRUE);
  475. }
  476.  
  477. static BOOL TreeSecondWalk(PNODE pThisNode,
  478.                            unsigned nCurrentLevel)
  479. {
  480.     /*------------------------------------------------------
  481.      * During a second pre-order walk, each node is given a
  482.      * final x-coordinate by summing its preliminary
  483.      * x-coordinate and the modifiers of all the node's
  484.      * ancestors.  The y-coordinate depends on the height of
  485.      * the tree.  (The roles of x and y are reversed for
  486.      * RootOrientations of EAST or WEST.)
  487.      * Returns: TRUE if no errors, otherwise returns FALSE.
  488.      *----------------------------------------------------*/
  489.  
  490.     BOOL  bResult = TRUE;       /* assume innocent        */
  491.     long  lxTemp, lyTemp;       /* hold calculations here */
  492.     float flNewModsum;          /* local modifier value   */
  493.     static float flModsum = (float)0.0;
  494.  
  495.     if (nCurrentLevel <= MAXIMUM_DEPTH) {
  496.         flNewModsum = flModsum; /* Save the current value */
  497.         switch (RootOrientation) {
  498.             case NORTH:
  499.                 lxTemp = (long)xTopAdjustment +
  500.                   (long)(pThisNode->flPrelim + flModsum);
  501.                 lyTemp = (long)yTopAdjustment +
  502.                   (long)(nCurrentLevel * LEVEL_SEPARATION);
  503.                 break;
  504.             case SOUTH:
  505.                 lxTemp = (long)xTopAdjustment +
  506.                   (long)(pThisNode->flPrelim + flModsum);
  507.                 lyTemp = (long)yTopAdjustment -
  508.                   (long)(nCurrentLevel * LEVEL_SEPARATION);
  509.                 break;
  510.             case EAST:
  511.                 lxTemp = (long)xTopAdjustment +
  512.                   (long)(nCurrentLevel * LEVEL_SEPARATION);
  513.                 lyTemp = (long)yTopAdjustment -
  514.                   (long)(pThisNode->flPrelim + flModsum);
  515.                 break;
  516.             case WEST:
  517.                 lxTemp = (long)xTopAdjustment -
  518.                   (long)(nCurrentLevel * LEVEL_SEPARATION);
  519.                 lyTemp = (long)yTopAdjustment -
  520.                   (long)(pThisNode->flPrelim + flModsum);
  521.                 break;
  522.         }
  523.  
  524.         if (CheckExtentsRange(lxTemp, lyTemp)) {
  525.             /* The values are within the allowable range  */
  526.             pThisNode->xCoordinate = (COORD)lxTemp;
  527.             pThisNode->yCoordinate = (COORD)lyTemp;
  528.  
  529.             if (HasChild(pThisNode)) {
  530.                 /* Apply the flModifier value for this    */
  531.                 /* node to all its offspring.             */
  532.                 flModsum = flNewModsum =
  533.                         flNewModsum + pThisNode->flModifier;
  534.                 bResult = TreeSecondWalk(
  535.                    FirstChild(pThisNode),nCurrentLevel + 1);
  536.                 flNewModsum = flNewModsum -
  537.                               pThisNode->flModifier;
  538.             }
  539.  
  540.             if ((HasRightSibling(pThisNode)) && (bResult)) {
  541.                 flModsum = flNewModsum;
  542.                 bResult = TreeSecondWalk(
  543.                     RightSibling(pThisNode), nCurrentLevel);
  544.             }
  545.         }
  546.         else bResult = FALSE;   /* outside of extents     */
  547.     }
  548.     return (bResult);
  549. }
  550.  
  551. static BOOL TreePosition(PNODE pApexNode)
  552. {
  553.     /*------------------------------------------------------
  554.      * Determine the coordinates for each node in a tree.
  555.      * Input: Pointer to the apex node of the tree
  556.      * Assumption: The x & y coordinates of the apex node
  557.      * are already correct, since the tree underneath it
  558.      * will be positioned with respect to those coordinates.
  559.      * Returns: TRUE if no errors, otherwise returns FALSE.
  560.      *----------------------------------------------------*/
  561.  
  562.     if (pApexNode) {
  563.         /* Initialize list of previous node at each level */
  564.         InitPrevNodeAtLevel();
  565.  
  566.         /* Generate the properly-placed tree nodes.       */
  567.         /* TreeFirstWalk: a post-order walk               */
  568.         /* TreeSecondWalk: a pre-order walk               */
  569.         if (TreeFirstWalk (pApexNode, FIRST_TIME)) {
  570.             /* Determine how to adjust the nodes with     */
  571.             /* respect to the location of the apex of the */
  572.             /* tree being positioned.                     */
  573.             switch (RootOrientation) {
  574.                 case NORTH:
  575.                 case SOUTH:
  576.                    /* Create the adjustment from x-coord  */
  577.                    xTopAdjustment = pApexNode->xCoordinate -
  578.                             (COORD)(pApexNode->flPrelim);
  579.                    yTopAdjustment = pApexNode->yCoordinate;
  580.                    break;
  581.                 case EAST :
  582.                 case WEST :
  583.                    /* Create the adjustment from y-coord  */
  584.                    xTopAdjustment = pApexNode->xCoordinate;
  585.                    yTopAdjustment = pApexNode->yCoordinate +
  586.                             (COORD)(pApexNode->flPrelim);
  587.                    break;
  588.             }
  589.             return (TreeSecondWalk(pApexNode, FIRST_TIME));
  590.         }
  591.         else return (FALSE); /* Couldn't get an element   */
  592.     }
  593.     else return (TRUE); /* Easy: null pointer was passed  */
  594. }
  595.